1. Deux questions du programme
Ce que l’on sait faire à la main, et ce que l’on ne sait plus faire.
Le programme de seconde pose deux questions sur les entiers :
Les deux algorithmes
1. Un entier naturel \(a\) est-il un multiple d’un entier naturel \(b\) ?
2. Quel est le plus grand multiple de \(a\) inférieur ou égal à \(b\) ?
À la main, la division euclidienne répond aux deux : \(b=aq+r\) avec \(0\leqslant r\lt a\) ; \(b\) est un multiple de \(a\) si et seulement si \(r=0\), et le plus grand multiple cherché est \(aq\). Mais qui poserait de tête la division de \(123\,456\,789\) par \(37\) ? Ce parcours construit une méthode, la teste sur un cas connu, puis la confie à une machine.
2. Euclide : retrancher tant que l’on peut
Alexandrie, vers 300 avant notre ère.
Dans le livre VII des Éléments, Euclide ne divise pas : il mesure. Un nombre en mesure un autre quand, retranché de lui autant de fois qu’on le peut, il l’épuise exactement. Sa définition 5 dit en substance : le plus grand nombre est un multiple du plus petit quand il est mesuré par le plus petit. Et ses premières propositions procèdent ainsi : « le plus petit étant retranché du plus grand, de manière continuelle… ».
Retranchons \(\) de \(\), tant que c’est possible :
Ce qui diffère du cours
Euclide n’écrit ni \(a=bq+r\) ni aucune lettre : il décrit des longueurs et des opérations en phrases. Mais le nombre de soustractions est notre quotient, et ce qui reste est notre reste.
3. La méthode d’Euclide en Python
Ajouter \(a\) tant que l’on ne dépasse pas \(b\) : c’est la même idée, à l’envers.
Le programme ci-dessous part de \(m=0\) et ajoute \(a\) tant que \(m+a\) ne dépasse pas \(b\) : à la fin, \(m\) est le plus grand multiple de \(a\) inférieur ou égal à \(b\). La seconde fonction s’en sert pour savoir si \(a\) est un multiple de \(b\). On le valide d’abord sur un cas connu : \(50=7\times 7+1\), donc la réponse doit être \(49\).
Si la console ne se charge pas, le même programme s’exécute sur https://sciency.co/console (nouvel onglet).
Lire le résultat
Le programme affiche \(49\), puis True False : \(49\) est un multiple de \(7\), \(50\) n’en est pas un. La méthode est validée sur le cas connu. Modifiez la dernière ligne pour essayer d’autres nombres.
plus_grand_multiple(, ) ?4. Plus court : le quotient et le reste
Python sait faire la division euclidienne en une instruction.
En Python, b // a donne le quotient et b % a le reste de la division euclidienne de \(b\) par \(a\). Les deux fonctions s’écrivent alors en une ligne chacune : remplacez-les dans la console, et vérifiez que les résultats ne changent pas.
5. Hors de portée de la main
Le cas que personne ne poserait de tête.
Écrivez dans la console print(plus_grand_multiple(, )), puis print( % ). Avec la version du quatrième écran, la réponse est immédiate ; avec celle du troisième, la boucle tourne des millions de fois (essayez : quelques secondes d’attente).
6. Un nombre qui en cache trois
\(1001\), et les nombres qui se répètent.
Essayez print(est_multiple(, )) : la console répond True. Plus surprenant, elle répond True pour tous les nombres de six chiffres de la forme « abcabc », et aussi avec \(7\), \(11\) ou \(13\) à la place de \(\). Une boucle peut les tester tous :
La machine vérifie les \(900\) cas sans trouver d’exception. Mais vérifier n’est pas démontrer : la question ci-dessous donne la raison.
7. Ce qu’il faut retenir
Une idée vieille de vingt-trois siècles, trois lignes de Python.
Les deux algorithmes
Le plus grand multiple de \(a\) inférieur ou égal à \(b\) est \(a\times q\), où \(q\) est le quotient de \(b\) par \(a\) : a * (b // a). Le nombre \(a\) est un multiple de \(b\) si et seulement si le reste est nul : a % b == 0.
Retrancher (ou ajouter) tant que l’on peut, comme Euclide, donne les mêmes résultats, mais en autant d’étapes que le quotient : c’est trop lent pour les grands nombres.
Votre parcours
Vous avez répondu à 0 question(s) sur 6 du premier coup.